package com.sheng.leetcode.year2023.month10.day25;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/10/25
 * <p>
 * 2698. 求一个整数的惩罚数<p>
 * <p>
 * 给你一个正整数 n ，请你返回 n 的 惩罚数 。<p>
 * n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：<p>
 * 1 <= i <= n<p>
 * i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 10<p>
 * 输出：182<p>
 * 解释：总共有 3 个整数 i 满足要求：<p>
 * - 1 ，因为 1 * 1 = 1<p>
 * - 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。<p>
 * - 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。<p>
 * 因此，10 的惩罚数为 1 + 81 + 100 = 182<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 37<p>
 * 输出：1478<p>
 * 解释：总共有 4 个整数 i 满足要求：<p>
 * - 1 ，因为 1 * 1 = 1<p>
 * - 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。<p>
 * - 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。<p>
 * - 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。<p>
 * 因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 1000<p>
 */
public class LeetCode2698 {

    @Test
    public void test01() {
//        int n = 10;
        int n = 37;
        System.out.println(new Solution().punishmentNumber(n));
    }
}

class Solution {
    public int punishmentNumber(int n) {
        // 所有满足 1 <= i <= n，同时满足 i * i 划分为子字符串之后和等于 i
        // 如何验证这个条件？
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            // 判断是否满足条件
            if (determine(String.valueOf(i * i), 0, i)) {
                ans += i * i;
            }
        }
        return ans;
    }

    /**
     * 判断字符串 s 是否满足条件
     *
     * @param s 字符串 s
     * @param i 字符串 s 中获取的索引起始位置
     * @param x 从字符串 s 中获取的子字符串的总和
     * @return
     */
    public boolean determine(String s, int i, int x) {
        // 获取字符串 s 的长度 m
        int m = s.length();
        if (i >= m) {
            return x == 0;
        }
        int y = 0;
        // 从索引位置 i 开始，进行循环
        for (int j = i; j < m; j++) {
            // 将 y 乘 10，获取 j 位置上的字符，并转化为整型加到 y 上
            y = y * 10 + (s.charAt(j) - '0');
            // 如果此时 y 大于等于 x，代表剩余子字符串之和超过 x，结束循环
            if (y > x) {
                break;
            }
            // 遍历
            if (determine(s, j + 1, x - y)) {
                return true;
            }
        }
        return false;
    }
}
